#pragma once

#include <map>
#include <set>
#include <deque>
#include <vector>
#include <unordered_set>

typedef enum TokenType {
	KW_INT = 0,		// int
	KW_VOID,		// void
	KW_RETURN,		// return
	KW_CONST,		// const
	
	OP_ADD,			// +
	OP_SUB,			// -
	OP_MUL,			// *
	OP_DIV,			// /
	OP_MOD,			// %
	OP_ASSIGN,		// =
	OP_GT,			// >
	OP_LT,			// <
	OP_EQ,			// ==
	OP_LE,			// <=
	OP_GE,			// >=
	OP_NE,			// !=
	OP_AND,			// &&
	OP_OR,			// ||

	SE_LBRAC,		// ( left backet
	SE_RBRAC,		// ) right bracket
	SE_LCBRAC,		// { left curly bracket
	SE_RCBRAC,		// } right curly bracket
	SE_COMMA,		// ,
	SE_SEMI,		// ;

	IDN,			// [a-zA-Z][a-zA-Z_0-9]*
	INT_VAL,		// -*[0-9]+
} TokenType;

typedef enum CharType {
	LETTER = 0,		// 字母					0
	UNDERLINE,		// _ 					1
	DIGIT,			// 数字					2

	ADD,			// +					3
	SUB,			// -					4
	MUL,			// *					5
	DIV,			// /					6
	MOD,			// %					7
	EQ,				// =					8
	GT,				// >					9
	LT,				// <					10
	NOT,			// !					11
	AND,			// &					12
	OR,				// |					13

	LBRAC,			// (					14
	RBRAC,			// )					15
	LCBRAC,			// {					16
	RCBRAC,			// }					17
	COMMA,			// ,					18
	SEMI,			// ;					19

	EPSILON,		// 空字符				20
} CharType;

typedef enum StateType {
	START,			// 初态
	INTER,			// 中间状态
	EXIT,			// 退出
} StateType;

class Token {
public:
	int ty;			// Token类别
	char *val;		// Token值

	Token(int _ty, char *_val);
	std::string grammar_name();
};

class NFA {
	std::map<int, int> state_types;
	std::map<int, int> state_vals;
	std::vector<std::map<int, std::vector<int>>>rules;

public:
	int state_num, char_num;

	NFA(const char *rule_file);

	void print_rules();

	void closure(const std::unordered_set<int> &init, std::unordered_set<int> &result) const;
	void go(const std::unordered_set<int> &src, CharType ty, std::unordered_set<int> &dst) const;

	int get_state_type(int state);
	int get_state_val(int state);
};

class DFA {
	FILE* infile;							// C文件指针
	int state_num, char_num;				// 状态个数和字符类别数量
	std::deque<char> buffer;				// 从文件中读取字符的缓存区
	std::map<int, int> state_types;			// 状态类型：START, INTER, EXIT
	std::map<int, int> state_vals;			// 退出状态返回的Token类型：OP_ADD, OP_SUB, ..., IDN, INT_VAL
	std::vector<std::map<int, int>> rules;	// 存储了DFA的状态转移规则

	char *dump(int len);					// 从缓存区首部弹出len长度字符串，并用动态内存保存，返回对应指针
	void pop(int len);						// 弹出但不保存
	bool is_inside(int, std::vector<int> &);
	void split_set(std::vector<int> &, int, std::vector<std::vector<int>> &);
	void remapping(std::vector<std::vector<int>> &, std::vector<std::map<int, int>> &, std::map<int, int> &, std::map<int, int> &);

public:
	DFA(NFA &nfa);											// 以NFA进行构造
	void print_rules();										// 打印DFA的状态转移规则

	bool is_same_type(int state0, int state1); 				// 检查两个状态是否为同一类型状态
	void first_split(std::vector<std::vector<int>> &sets);	// 根据各状态的类型进行初次划分
	void split_set(std::vector<int> &set);					// 根据DFA状态转移规则划分集合
	void minimise();										// DFA最小化

	void openfile(char *input_file);						// 打开C文件
	void closefile();										// 关闭C文件

	int get_token(Token &tk);								// 获取一个token，返回值0表示成功获取，返回值1表示文件读取完
};

typedef std::vector<std::pair<std::string, int>> SymTab;	// first:val; second: type;

void init_sym_tab();
void make_tokens(DFA &dfa, char *input, std::vector<Token> &tokens);
void print_tokens(std::ostream &, std::vector<Token> &);
